package sortAlgorithm;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] a = { 3, 2, 5, 7, 6, 9};
		mergeSort(a);
		System.out.println(Arrays.toString(a));
	}
	/**
	 * 归并排序
	 * @param array	待排数组
	 */
	public static void mergeSort(int[] array) {
		mergeSort(array,0,array.length-1);
	}
	/**
	 * 归并排序
	 * @param array	待排数组
	 * @param begin	开始下标
	 * @param end	结束下标
	 */
	private static void mergeSort(int[] array,int begin,int end) {
		if(begin<end) {
			int mid = begin+((end-begin)>>1);
			mergeSort(array,begin,mid);
			mergeSort(array,mid+1,end);
			merge(array,begin,mid,end);
		}
	}
	/**
	 * 归并合并
	 * @param array	待排数组
	 * @param begin	开始下标
	 * @param mid	中间下标
	 * @param end	结束下标
	 */
	private static void merge(int[] array,int begin,int mid,int end) {
		int[] helper = new int[array.length];	//array副本
		int k=0,current=begin;	//current从begin开始
		for (int i : array) {
			helper[k++] = i;
		}
		int left = begin,right = mid+1;
		while(left<=mid&&right<=end) {
			if(helper[left]<=helper[right]) {
				array[current++]=helper[left++];
			}else {
				array[current++]=helper[right++];
			}
		}
		while(left<=mid) {
			array[current++]=helper[left++];
		}
	}
}
